package searchcode;

public class Binary {
    public static void main(String[] args) {
        //  1.二分查找非递归
        int[] arr = {2, 3, 5, 12, 22, 34, 35, 67};
        int index = binary(arr, 121);
        System.out.println(index);
        // 2.二分查找递归
        int[] arr1 = {2, 3, 5, 12, 22, 34, 35, 67};
        int index1 = binaryRecursion(arr1, 0,arr.length-1,1212);
        System.out.println(index1);
    }

    // 1.二分查找非递归
    public static int binary(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }

    // 2.二分查找递归
    public static int binaryRecursion(int[] arr, int low, int high, int target) {
        if (low > high) return -1;
        int mid = (low + high) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            return binaryRecursion(arr, low, mid-1, target);
        } else {
            return binaryRecursion(arr, mid+1, high, target);
        }
    }
}

